package com.future;

/**
 * Description: 123. ������Ʊ�����ʱ�� III (��ˢ��15��ֻ��Ҫ����leetcode 188�Ϳ�����)
 * ����һ�����飬���ĵ� i ��Ԫ����һ֧�����Ĺ�Ʊ�ڵ� i ��ļ۸�
 * <p>
 * ���һ���㷨�����������ܻ�ȡ��������������������?����?���ס�
 * <p>
 * ע�⣺�㲻��ͬʱ�����ʽ��ף���������ٴι���ǰ���۵�֮ǰ�Ĺ�Ʊ����
 * <p>
 * ?
 * <p>
 * ʾ��?1:
 * <p>
 * ���룺prices = [3,3,5,0,0,3,1,4]
 * �����6
 * ���ͣ��ڵ� 4 �죨��Ʊ�۸� = 0����ʱ�����룬�ڵ� 6 �죨��Ʊ�۸� = 3����ʱ����������ʽ������ܻ������ = 3-0 = 3 ��
 * ?    ����ڵ� 7 �죨��Ʊ�۸� = 1����ʱ�����룬�ڵ� 8 �� ����Ʊ�۸� = 4����ʱ����������ʽ������ܻ������ = 4-1 = 3 ��
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @author weiruibai.vendor
 * Date: 2022/5/7 11:12
 */
public class Solution_123 {

    public static void main(String[] args) {
        int[] prices = {3, 2, 6, 5, 0, 3};
        prices = new int[]{3, 1, 2, 9, 2, 3, 6, 8};
        prices = new int[]{1, 2};

        prices = new int[]{3, 3, 5, 0, 0, 3, 1, 4};


        System.out.println(maxProfit(prices));
    }

    /**
     * ����ʵ����<188. ������Ʊ�����ʱ�� IV>�Ľ���
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int[] prices) {
        int k = 2;
        if (prices == null || prices.length == 0 || k <= 0) {
            return 0;
        }
        int N = prices.length;
        if (k >= N / 2) {
            return allSegment(prices);
        }
        int[][] dp = new int[N][k + 1];
        for (int col = 1; col < k + 1; col++) {
            // ��¼����ǰһ�����ֵ
            int preBest = dp[0][col - 1] - prices[0];
            /**
             * dp[1][col] :
             * 1��dp[0][col]
             * 2��dp[0][col-1]+[col]-[0]
             */
            dp[1][col] = Math.max(dp[1][col - 1], preBest + prices[col]);
            int max = 0;
            for (int row = 1; row < N; row++) {
                /**
                 * dp[i][j] ֵΪ������������ֵ
                 * 1��dp[i-1][j] ---������Ե����ó���
                 * 2��dp[i-1][j-1] + prices[i]-prices[i-1]
                 * ------------------------------------------
                 * 3��dp[i-2][j-1] + prices[i]-prices[i-2]
                 * 4��dp[i-3][j-1] + prices[i]-prices[i-3]
                 *  ...
                 *  dp[0][j-1] + prices[i]-prices[0]
                 *
                 * dp[i-1][j] ֵΪ������������ֵ
                 * 1��dp[i-2][j] ---������Ե����ó���
                 * 2��dp[i-2][j-1] + prices[i]-prices[i-2]
                 * 3��dp[i-3][j-1] + prices[i]-prices[i-3]
                 *  ...
                 *  dp[0][j-1] + prices[i]-prices[0]
                 *
                 *  ���dp[i][j]��dp[i-1][j]
                 *  preBest��¼����dp[i-1][j]�е�
                 * 1��dp[i-2][j-1] -prices[i-2]
                 * 2��dp[i-3][j-1] -prices[i-3]
                 *  ...
                 *  dp[0][j-1] -prices[0]
                 *  �����ֵ
                 *
                 *  ��ôdp[i][j] =
                 * 1��dp[i-1][j] ---������Ե����ó���
                 * 2��dp[i-1][j-1] + prices[i]-prices[i-1]
                 * 3��preBest + prices[i]
                 * �е����ֵ
                 *
                 */
                preBest = Math.max(preBest, dp[row - 1][col - 1] - prices[row - 1]);
                max = Math.max(max, preBest + prices[row]);
                dp[row][col] = Math.max(max, dp[row - 1][col]);
            }
        }
        return dp[N - 1][k];
    }

    private static int allSegment(int[] prices) {
        int maxProfit = 0;
        int N = prices.length;
        int minFragment = prices[0];
        int maxFragment = prices[0];
        int L = 1;
        while (L < N) {
            int val = prices[L];
            if (val < maxFragment) {
                maxProfit += (maxFragment - minFragment);
                minFragment = val;
            }
            maxFragment = val;
            L++;
        }
        if (maxFragment > minFragment) {
            maxProfit += (maxFragment - minFragment);
        }
        return maxProfit;
    }
}
